package zuo.algo.c19;

/**
 * 01:33
 * 给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
 * 例如:
 * 01111
 * 01001
 * 01001
 * 01111
 * 01011
 * 其中边框全是1的最大正方形的大小为4*4，所以返回4。
 */
public class A05 {

    public static int exc1(int[][] matrix) {
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            int[] arr = matrix[i];
            for (int j = 0; j < arr.length; j++) {
                if (matrix[i][j] == 0) {
                    continue;
                }
                int count1 = 1;
                while ((j + count1) < arr.length) {
                    if (matrix[i][j + count1] == 0) {
                        break;
                    }
                    count1++;
                }
                int count2 = 1;
                while ((i + count2) < matrix.length) {
                    if (matrix[i + count2][j] == 0) {
                        break;
                    }
                    count2++;
                }
                int count = Math.min(count1, count2);
                if (count < res) {
                    continue;
                }
                out: for (int m = 1; m < count; m++) {
                    int x = i + m;
                    int y = j + m;
                    for (int n = 1; n <= m; n++) {
                        if (matrix[x][j + n] == 0 || matrix[i + n][y] == 0) {
                            continue out;
                        }
                    }
                    res = Math.max(res, m + 1);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][] {
                {0, 1, 1, 1, 1},
                {0, 1, 0, 0, 1},
                {0, 1, 0, 0, 1},
                {0, 1, 1, 1, 1},
                {0, 1, 0, 1, 1}
        };
        int res = exc1(matrix);
        System.out.println(res);
    }
}
